#include <stdio.h>

/*
  1. 链表反转
  2. 链表中环的检测
  3. 两个有序的链表合并
  4. 删除链表倒数的第N个节点
  5. 寻找链表的中间节点
*/

/* 单链表结构体 */
typedef struct node
{
    int val;
    struct node *next;
} ListNode;

void print(ListNode *head);

/* 链表反转 */
ListNode *reverse(ListNode *head);
void testReverse();

/* 检测链表是否有环 */
ListNode *detectCycle(ListNode *head);
void testDetectCycle();

/* 两个有序的链表合并 */
ListNode *merge(ListNode *l1, ListNode *l2);
void testMerge();

/* 删除链表倒数的第N个节点 */
ListNode *removeFromEnd(ListNode *head, int n);
void testRemoveFromEnd();

/* 寻找链表的中间节点 */
ListNode *middle(ListNode *head);
void testMiddle();

void main()
{
    // testReverse();

    // testDetectCycle();

    // testMerge();

    // testRemoveFromEnd();

    testMiddle();
}

/*
    解题思路：
        1. 先获取 pre curr next 节点，第一次初始化为 pre=null curr=head next=curr.next；
        2. 循环终止条件为 curr != null，将 curr 的下一节点赋值为 pre，pre 赋值为 curr，curr 赋值为 next；
        3. 这样就实现了每一次循环中，会将 curr 和 pre 实现反转，循环至尾结点，即实现了链表反转
*/
ListNode *reverse(ListNode *head)
{
    if (head == NULL)
        return NULL;

    ListNode *pre = NULL;
    ListNode *curr = head;

    while (curr != NULL)
    {
        ListNode *next = curr->next;
        curr->next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}

void testReverse()
{
    ListNode a, b, c;
    a.val = 1;
    a.next = &b;
    b.val = 2;
    b.next = &c;
    c.val = 3;
    c.next = NULL;

    ListNode *reversed = reverse(&a);

    while (reversed != NULL)
    {
        printf("%d\n", reversed->val);
        reversed = reversed->next;
    }
}

/*
    解题思路：
        1. 定义快慢指针，快指针每次走两步，慢指针每次走一步，慢指针必定在进入环内未走完一圈时与快指针相遇
        2. 相遇后，快指针从头节点开始走，慢指针接着在环内走，如果再次相遇，就是链表环的起点
*/
ListNode *detectCycle(ListNode *head)
{
    if (head == NULL)
        return NULL;

    ListNode *fast = head;
    ListNode *slow = head;
    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            fast = head;
            while (fast != slow)
            {
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }
    }
    return NULL;
}

void testDetectCycle()
{
    ListNode a, b, c, d;
    a.val = 1;
    a.next = &b;
    b.val = 2;
    b.next = &c;
    c.val = 3;
    c.next = &d;
    d.val = 4;
    d.next = &b;

    ListNode *cycleNode = detectCycle(&a);
    printf("cycle node: %d\n", cycleNode->val);
}

/*
    解题思路：
        1. 定义 head 和 pre 节点，head 节点为哨兵节点，最后返回 head->next 节点
        2. 首先判断 l1 和 l2 都不为空的情况，比较节点值大小，小的先行赋值给 pre，再继续进行比较
        3. 当一个链表已经比较结束后，剩下的另一个链表由于本身是有序的，无需再比较了，直接将 pre->next 指向链表剩下的节点即可
*/
ListNode *merge(ListNode *l1, ListNode *l2)
{
    if (!l1)
        return l2;
    if (!l2)
        return l1;

    ListNode h;
    h.val = -1;
    h.next = NULL;

    ListNode *head = &h, *pre = &h;

    while (l1 != NULL && l2 != NULL)
    {
        if (l1->val < l2->val)
        {
            pre->next = l1;
            pre = pre->next;
            l1 = l1->next;
        }
        else
        {
            pre->next = l2;
            pre = pre->next;
            l2 = l2->next;
        }
    }

    if (l1 != NULL)
    {
        pre->next = l1;
    }
    if (l2 != NULL)
    {
        pre->next = l2;
    }
    return head->next;
}

void testMerge()
{
    ListNode a, b, c, d, e, f;
    a.val = 1;
    a.next = &b;
    b.val = 2;
    b.next = &c;
    c.val = 3;
    c.next = NULL;

    d.val = 1;
    d.next = &e;
    e.val = 4;
    e.next = &f;
    f.val = 5;
    f.next = NULL;

    ListNode *meraged = merge(&a, &d);
    while (meraged != NULL)
    {
        printf("%d\n", meraged->val);
        meraged = meraged->next;
    }
}

/*
    解题思路：
        1. 首先定义快慢指针，快指针先走 n 步，然后快慢指针再一起走
        2. 当快指针走到末尾时，慢指针就是要删除的节点
*/
ListNode *removeFromEnd(ListNode *head, int n)
{
    if (!head)
        return NULL;

    ListNode *fast = head, *slow = head;
    ListNode *pre;
    for (int i = 0; i < n; i++)
    {
        fast = fast->next;
    }

    while (fast)
    {
        fast = fast->next;
        pre = slow;
        slow = slow->next;
    }

    if (slow == head)
    {
        return head->next;
    }

    // 此时 slow 就是要删除的节点
    pre->next = slow->next;
    return head;
}

void testRemoveFromEnd()
{
    ListNode a, b, c, d, e, f;
    a.val = 1;
    a.next = &b;
    b.val = 2;
    b.next = &c;
    c.val = 3;
    c.next = &d;
    d.val = 4;
    d.next = &f;
    f.val = 5;
    f.next = NULL;

    ListNode *removed = removeFromEnd(&a, 2);
    while (removed)
    {
        printf("%d\n", removed->val);
        removed = removed->next;
    }
}

/*
    解题思路：
        1. 定义快慢指针，快指针每次走2不，慢指针每次走1步
        2. 当快指针走到末尾时，慢指针就刚好在中间节点上

*/
ListNode *middle(ListNode *head)
{
    if (!head->next)
    {
        return head;
    }

    ListNode *fast = head, *slow = head;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

void testMiddle()
{
    ListNode a, b, c, d, e, f;
    a.val = 1;
    a.next = &b;
    b.val = 2;
    b.next = NULL;
    // c.val = 3;
    // c.next = &d;
    // d.val = 4;
    // d.next = &f;
    // f.val = 5;
    // f.next = NULL;

    ListNode *middleNode = middle(&a);
    print(middleNode);
}

void print(ListNode *head)
{
    while (head)
    {
        printf("%d\n", head->val);
        head = head->next;
    }
}